1. Field of the Invention
The present invention relates to a method and apparatus for providing volume graphics. More particularly, the present invention relates to a method and apparatus for providing efficient space leaping using a neighbor guided emptiness map.
2. Description of the Related Art
Volume graphics is the subfield of computer graphics that deals with the visualization of objects or phenomena represented as sampled data in three or more dimensions. These samples are called volume elements, or “voxels,” and contain digital information representing physical characteristics of the objects or phenomena being studied. For example, voxel data for a particular object may represent density, type of material, temperature, velocity, or some other property at discrete points in space throughout the interior and in the vicinity of the object.
Voxel-based representations of objects occur in many situations and applications. For example, tomographic scans and nuclear magnetic resonance scans of a human body or industrial assembly produce three dimensional arrays of data representing the density and type of material comprising the body or object.
In the past, two methods have been available for this purpose. One method is to construct a series of parallel two-dimensional image slices, each representing a slightly different cross section of the object being viewed. This is the method typically used by radiologists when viewing computed tomography scans or nuclear magnetic resonance scans of the human body. Radiologists are trained to construct three-dimensional mental pictures of the internal organs of the body from these series of two-dimensional images. The slices are, in general, parallel to one of the primary dimensions or axes of the body, so that they represent the “sagittal,” “axial,” and “coronal” views that are familiar to radiologists. This method of visualizing voxel-based data is difficult, requires years of training, and is prone to uncertainty, even by the most expert practitioners.
Another method is to convert voxel data into representations suitable for computer graphics systems to display. Most computer graphic systems today are designed to display surfaces of objects by subdividing those surfaces into small triangles or polygons. These triangles are assigned colors and levels of transparency or opacity, then converted into pixels, that is picture elements, and projected onto the computer screen. Triangles corresponding to surfaces in the foreground obscure those corresponding to surfaces in the background. Triangles can also be colored or painted with textures and other patterns to make them look more realistic. Additional realism is made possible by simulating the position and effects of lights, so that highlights and shadows appear on the resulting image. The art and science of this kind of graphics system is well-developed and described by a large body of literature such as the textbook “Computer Graphics: Principles and Practice,” 2.sup.nd edition, by J. Foley, A. vanDam, S. Feiner, and J. Hughes, published by Addison-Wesley of Reading, Mass., in 1990, which is incorporated herein in its entirety by reference.
In recent years, an alternative method has emerged called volume rendering. Specifically, the process of creating a viewable image from computer data is called “rendering,” and the process of creating a viewable image from voxel data is called “volume rendering”. More specifically, this method is a form of digital signal processing in which the individual voxels of a voxel-based representation are assigned colors and levels of transparency or opacity. The mechanism for mapping the data values of individual voxels to colors and transparencies is called a “transfer function”. The voxels are then projected onto a two-dimensional viewing surface such as a computer screen, with opaque voxels in the foreground obscuring other voxels in the background. This accumulation of projected voxels results in a visual image of the object. Lighting calculations can be done on the individual voxels to create the appearance of highlights and shadows in a similar manner to that of conventional computer graphics.
By changing the assignment of colors and transparency to particular voxel data values, different views of the exterior and interior of an object can be seen. For example, a surgeon who needs to examine the ligaments, tendons, and bones of a human knee in preparation for surgery can utilize a tomographic scan of the knee and cause voxel data values corresponding to blood, skin, and muscle to appear to be completely transparent. In another example, a mechanic using a tomographic scan of a turbine blade or weld in a jet engine can cause voxel data values representing solid metal to appear to be transparent while causing those representing air to be opaque. This allows the viewing of internal flaws in the metal that would otherwise be hidden from the human eye.
It should be noted that there are a number of techniques to take the data points or voxels representing an object and project them onto a flat viewing surface such as a computer screen. In each of these techniques, an object to be viewed is positioned relative to the viewing surface by translating the three dimensional sampled data representing that object to the spatial coordinates of the space in front of or behind the viewing surface. The techniques consist of different methods of computing the color and intensity of the light at discrete points or “pixels” on that viewing surface.
Direct volume rendering is an important technique for visualizing 3-D medical datasets. With advancements in computational processing and medical devices, the size of the 3D volumetric datasets are rapidly increasing. The “Visible Human Project” from the National Library of Medicine produced massive datasets having the size of 512×512×1728 (864 MB). The new Computed Tomography (CT) machine from Siemens Medical, for example, can generate a dataset having the size of 512×512×4096. The interactivity of the rendering tool is very important for medical professionals to diagnose diseases based on such large datasets.
Direct volume rendering has been well researched by the visualization community. Ray-casting, Splatting, Shear-warp and 3D texture mapping are the most common volume rendering techniques. Among these technologies Ray-casting can generate the highest quality images and the algorithms scale well with the increase of the dataset size as disclosed in M. Levoy, “Display of Surfaces From Volume Data”, IEEE Computer Graphics and Applications, 8(5):29-37, 1988, which is incorporated herein by reference in its entirety. However, interactivity is difficult to achieve using the brute-force approach due to the intensive memory access requirement and computational processing requirement of the algorithm.
Similarly, shear-warping is currently considered the fastest software based technique. Unfortunately, this method suffers from artifacts due to insufficient sampling rates along the z-axis and the bilinear interpolation. One solution is to use trilinear interpolation and super-sampling as implemented in Volume Pro as disclosed in H. Pfister, J. Hardenbergh, J. Knittel, H. Lauer, and L. Seiler, “Volume Pro Real-Time Ray-Casting System”, SIGGRAPH.99, pp. 251-260, the entire contents of which is incorporated herein in its entirety by reference. However, the data size is limited to no more than 2563 due to the memory size on the board.
The additional data structure like octree disclosed in M. Levoy. “Efficient Ray Tracing of Volume Data”, ACM Transactions on Graphics, 9(3), 1990, 245-261, which is incorporated herein in its entirety by reference, is proposed to efficiently skip empty space in the volume. However, this is not adequately done to overcome the problems of artifacts.
Thus, there is a need for a system and method for reducing memory access when traversing octrees thus mitigating cache misses and speeding up the rendering without the problems encountered in the prior art.